Fast and efficient capacitance extraction is the cornerstone of integrated circuit electrical evaluation. For the past decade, a number of different approaches have been proposed to analyze capacitance. These approaches can be divided into two categories, one being deterministic techniques, such as boundary element or finite difference methods, and the other being stochastic techniques, such as floating random walk. In general, deterministic techniques involve solving linear system functions. However, for large integrated circuit geometries, the time needed to obtain the linear system solutions dominates the computational complexity. Different acceleration tools (“fast-solvers”), such as pre-corrected fast Fourier transform, multipole expansion and hierarchical techniques, have been proposed to speed up the system solves.
Even with these enhancement tools, deterministic techniques prove to be too inefficient for use with complex designs that involve a very large number of similar configurations. Take for example, the generation of capacitance tables used in macro and full-chip parasitic layout extraction and the generation of parameterized reduced-order models used in timing and noise analysis. Such models require the presolution of a large number of similar configurations to build a representative set of capacitances corresponding to a representative set of parameters. Another example is the extraction of capacitance distributions as is found in a number of stochastic extraction techniques, such as the stochastic collocation algorithm. All of these examples require as a fundamental step the solution of a very large number of similar configurations.
FIG. 1 is image 100 illustrating wafer contours present in an active area of a static random access memory (SRAM) cell designed in a 45 nanometer (nm) technology. The highly irregular contours shown in image 100 are present despite the use of lithographic improvement techniques such as optical pre-correction and resolution enhancement. While contour-aware extraction has been proposed to improve the accuracy of layout parasitics in the presence of lithographic irregularities, the highly irregular nature of these contours make such an approach very time consuming.
Lithography mainly impacts the layout shapes in mask planes. Chemical-mechanical polishing (CMP), on the other hand, contributes to uncertainties in interconnect heights perpendicular to the mask planes. These uncertainties further highlight a need for fast extraction techniques that can accommodate a large number of similar configurations.
Capacitance extraction in the context of a large number of similar configurations is generally implemented using an adjoint method, which facilitates computing the sensitivity of a capacitance matrix (more precisely a vector in the capacitance matrix) with respect to a large number of independent variations with a computational complexity independent of the number of parameters. However, the total time required to compute the sensitivities is approximately 2.5 times that required to solve the nominal system. There is still however, a vast amount of room for improvement, especially when large, complex design configurations are involved. With such complex design configurations, conventional approaches such as the adjoint method prove too inefficient for mainstream use.
Therefore, improved capacitance extraction techniques that can accommodate a large number of similar configurations would be desirable.